package org.apache.commons.graph.algorithms.shortestpath

import org.apache.commons.graph.Graph
import org.apache.commons.graph.Mapper
import org.apache.commons.graph.UndirectedGraph
import org.apache.commons.graph.VertexPair
import org.apache.commons.graph.weight.OrderedMonoid

/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

/**
 *
 * @param <V> the Graph vertices type.
 * @param <WE> the Graph weighted edges type
 * @param <W> the weight type
</W></WE></V> */
interface PathSourceSelector<V, WE, W> {
    /**
     * Calculates all vertices shortest paths using the FloydWarshall's algorithm.
     *
     * @param <WO> the type of weight operations
     * @param weightOperations the weight operations needed for the algorithm
     * @return a data structure which contains all vertex pairs shortest path.
    </WO> */
    fun <WO : OrderedMonoid<W>> applyingFloydWarshall(weightOperations: WO): AllVertexPairsShortestPath<V, WE, W>

    /**
     * Specifies the shortest path source.
     *
     * @param source
     */
    fun <H : V> from(source: H): TargetSourceSelector<V, WE, W>
}



/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

internal class DefaultPathSourceSelector<V, WE, W>(
    private val graph: Graph<V, WE>,
    private val weightedEdges: Mapper<WE, W>
) : PathSourceSelector<V, WE, W> {
    /**
     * {@inheritDoc}
     */
    override fun <WO : OrderedMonoid<W>> applyingFloydWarshall(weightOperations: WO): AllVertexPairsShortestPath<V, WE, W> {
//        var weightOperations = weightOperations
//        weightOperations = Assertions.checkNotNull(
//            weightOperations,
//            "Floyd-Warshall algorithm can not be applied using null weight operations"
//        )

        val shortestPaths = AllVertexPairsShortestPath<V, WE, W>(weightOperations)
        val next: MutableMap<VertexPair<V>, V> = HashMap()

        // init
        for (we in graph.edges) {
            val vertexPair = graph.getVertices(we)
            shortestPaths.addShortestDistance(vertexPair!!.head, vertexPair.tail, weightedEdges.map(we))

            if (graph is UndirectedGraph<*, *>) {
                shortestPaths.addShortestDistance(vertexPair.tail, vertexPair.head, weightedEdges.map(we))
            }
        }

        // run the Floyd-Warshall algorithm.
        for (k in graph.vertices) {
            for (i in graph.vertices) {
                for (j in graph.vertices) {
                    if (shortestPaths.hasShortestDistance(i, k) && shortestPaths.hasShortestDistance(k, j)) {
                        val newDistance = weightOperations.append(
                            shortestPaths.getShortestDistance(i, k)!!,
                            shortestPaths.getShortestDistance(k, j)!!
                        )
                        if (!shortestPaths.hasShortestDistance(i, j)
                            || weightOperations.compare(newDistance, shortestPaths.getShortestDistance(i, j)) < 0
                        ) {
                            shortestPaths.addShortestDistance(i, j, newDistance)

                            // store the intermediate vertex
                            next[VertexPair(i, j)] = k
                        }
                    }
                }
            }
        }

        // fills all WeightedPaths
        for (source in graph.vertices) {
            for (target in graph.vertices) {
                if (source != target) {
                    val predecessorsList =
                        org.apache.commons.graph.algorithms.shortestpath.PredecessorsList(
                            graph,
                            weightOperations,
                            weightedEdges
                        )

                    pathReconstruction(predecessorsList, source, target, next)
                    if (!predecessorsList.isEmpty) {
                        val weightedPath = predecessorsList.buildPath(source, target)
                        if (weightedPath.order > 0) {
                            shortestPaths.addShortestPath(source, target, weightedPath)
                        }
                    }
                }
            }
        }

        return shortestPaths
    }

    /**
     * {@inheritDoc}
     */
    override fun <H : V> from(source: H): TargetSourceSelector<V, WE, W> {
        //var source = source
        //source = Assertions.checkNotNull(source, "Shortest path can not be calculated from a null source")
        return DefaultTargetSourceSelector(graph, weightedEdges, source)
    }

    private fun pathReconstruction(
        path: org.apache.commons.graph.algorithms.shortestpath.PredecessorsList<V, WE, W>,
        source: V, target: V,
        next: Map<VertexPair<V>, V>
    ) {
        val k = next[VertexPair(source, target)]
        if (k == null) {
            // there is a direct path between a and b
            val edge: WE? = graph.getEdge(source, target)
            if (edge != null) {
                path.addPredecessor(target, source)
            }
        } else {
            pathReconstruction(path, source, k, next)
            pathReconstruction(path, k, target, next)
        }
    }
}